import json
from typing import List, Dict, Set, Optional
from collections import deque, defaultdict

class DAGDependencyResolver:
    def __init__(self, edges: List[List[str]] = None):
        """初始化 DAG 依赖解析器"""
        self.graph = defaultdict(list)  # 邻接表表示图
        self.reverse_graph = defaultdict(list)  # 逆邻接表，用于查找父节点
        self.nodes = set()  # 所有节点的集合
        
        if edges:
            self.build_graph(edges)
    
    def build_graph(self, edges: List[List[str]]) -> None:
        """从边列表构建图"""
        for edge in edges:
            if len(edge) < 2:
                continue  # 至少需要两个节点才能形成边
                
            for i in range(len(edge) - 1):
                parent, child = edge[i], edge[i+1]
                self.graph[parent].append(child)
                self.reverse_graph[child].append(parent)
                self.nodes.add(parent)
                self.nodes.add(child)
    
    def get_dependencies(self, node: str) -> List[str]:
        """获取节点的所有依赖，按逆拓扑排序"""
        if node not in self.nodes:
            raise ValueError(f"节点 '{node}' 不在图中")
            
        # 使用 BFS 收集所有依赖节点
        visited = set()
        queue = deque([node])
        visited.add(node)
        
        while queue:
            current = queue.popleft()
            for parent in self.reverse_graph.get(current, []):
                if parent not in visited:
                    visited.add(parent)
                    queue.append(parent)
        
        # 对收集到的节点进行拓扑排序
        sorted_nodes = self._topological_sort(visited)
        
        # 反转排序结果，使节点按依赖顺序排列
        return sorted_nodes[::-1]
    
    def _topological_sort(self, nodes: Set[str]) -> List[str]:
        """对给定节点集合进行拓扑排序"""
        # 计算每个节点的入度
        in_degree = {node: 0 for node in nodes}
        for node in nodes:
            for child in self.graph.get(node, []):
                if child in nodes:
                    in_degree[child] += 1
        
        # 初始化队列，将入度为0的节点加入队列
        queue = deque([node for node in nodes if in_degree[node] == 0])
        result = []
        
        while queue:
            current = queue.popleft()
            result.append(current)
            
            # 减少相邻节点的入度
            for child in self.graph.get(current, []):
                if child in nodes:
                    in_degree[child] -= 1
                    if in_degree[child] == 0:
                        queue.append(child)
        
        return result

def load_from_config(file_path: str) -> DAGDependencyResolver:
    """从配置文件加载图"""
    try:
        with open(file_path, 'r') as f:
            config = json.load(f)
            edges = config.get('edges', [])
            return DAGDependencyResolver(edges)
    except FileNotFoundError:
        raise FileNotFoundError(f"配置文件 '{file_path}' 不存在")
    except json.JSONDecodeError:
        raise ValueError(f"配置文件 '{file_path}' 不是有效的 JSON 格式")

if __name__ == "__main__":
    edges = [
        ['A', 'B', 'C', 'D'],
        ['B', 'E', 'F'],
        ['B', 'G', 'F'],
        ['H', 'G']
    ]
    
    resolver = DAGDependencyResolver(edges)
    
    print("D 的依赖:", resolver.get_dependencies("D"))  
    print("G 的依赖:", resolver.get_dependencies("G"))  
